﻿#define _CRT_SECURE_NO_WARNINGS 1



//把这些源点汇聚在⼀起，当成⼀个"超级源点"。
// 然后从这个"超级源点"开始，处理最短路问题。落实到代码上时：
//1. 初始化的时候，把所有的源点都加⼊到队列⾥⾯；
//2. 然后正常执⾏ bfs 的逻辑即可。
//也就是初始化的时候，⽐普通的 bfs 多加⼊⼏个起点。


//https://ac.nowcoder.com/acm/problem/51024




//正难则反：将每个终点1看作起点，进行BFS



//#include<iostream>
//#include<queue>
//#include<cstring>
//
//using namespace std;
//
//typedef pair<int, int> PII;
//const int N = 1010;
//
//int n, m;
//char a[N][N];
//int dist[N][N];
//int d[] = { -1,0,1,0,-1 };
//
//void bfs()
//{
//    memset(dist, -1, sizeof dist);
//
//    queue<PII> q;
//    //1.将源头都存进队列q中
//    for (int i = 1;i <= n;i++)
//    {
//        for (int j = 1;j <= m;j++)
//        {
//            if (a[i][j] == '1')
//            {
//                dist[i][j] = 0;
//                q.push({ i,j });
//            }
//        }
//    }
//    //正常BFS
//    while (q.size())
//    {
//        auto t = q.front();q.pop();
//        int i = t.first;
//        int j = t.second;
//        for (int k = 0;k < 4;k++)
//        {
//            int x = i + d[k];
//            int y = j + d[k + 1];
//            if (x >= 1 && x <= n && y >= 1 && y <= m && dist[x][y] == -1)
//            {
//                dist[x][y] = dist[i][j] + 1;
//                q.push({ x,y });
//            }
//        }
//    }
//}
//
//int main()
//{
//    cin >> n >> m;
//    for (int i = 1;i <= n;i++)
//        for (int j = 1;j <= m;j++)
//            cin >> a[i][j];
//    bfs();
//
//    for (int i = 1;i <= n;i++)
//    {
//        for (int j = 1;j <= m;j++)
//            cout << dist[i][j] << " ";
//        cout << endl;
//    }
//    return 0;
//}